﻿#define _CRT_SECURE_NO_WARNINGS 1
//函数递归的使用
//#include<stdio.h>
//
//int main()
//{
//	printf("haha\n");
//	main();
//
//	return 0;
//}

//函数递归的限制条件
//递归在书写的时候，有2个必要条件：
//• 递归存在限制条件，当满⾜这个限制条件的时候，递归便不再继续。
//• 每次递归调⽤之后越来越接近这个限制条件

//举例：计算n的阶乘（不考虑溢出），n的阶乘就是1~n的数字累积相乘。
//#include<stdio.h>
//
////递归的方式实现
//int Fac(int n)
//{
//	if (n == 0)
//		return 1;
//	else
//		return n * Fac(n - 1);
//}
//
////迭代的方式实现
////int Fac(int n)
////{
////	int ret = 1;
////	int i = 0;
////	for (i = 1; i <= n; i++)
////	{
////		ret *= i;
////	}
////
////	return ret;
////}
//
//int main()
//{
//	int n = 0;
//	scanf("%d", &n);
//	int num = Fac(n);
//
//	printf("%d\n", num);
//
//	return 0;
//}

//输⼊⼀个整数m，按照顺序打印整数的每⼀位。
//⽐如：
//输⼊：1234 输出：1 2 3 4
//输⼊：520 输出：5 2 0

//#include<stdio.h>
//
//void Print(int m)
//{
//	if (m > 9)
//	{
//		Print(m / 10);
//	}
//		
//	printf("%d ", m % 10);
//}
//
//int main()
//{
//	int m = 0;
//	scanf("%d", &m);
//
//	Print(m);
//}

//求第n个斐波那契数
#include<stdio.h>

//递归方式实现，当n是一个很大的数时，那么在时间上就会有些开销
//int Fib(int n)
//{
//	if (n <= 2)
//	{
//		return 1;
//	}
//
//	return Fib(n - 1) + Fib(n - 2);
//}

//循环的方式实现
//int Fib(int n)
//{
//	// 1 1 2 3 5 8 13 21
//	// 1 2 3 4 5 6 7  8
//	int a = 1;
//	int b = 1;
//	int c = 1;
//	while (n > 2)
//	{
//		c = a + b; 
//		a = b;
//		b = c;
//		n--;
//	}
//
//	return c;
//}
//
//int main()
//{
//	int n = 0;
//	scanf("%d", &n);
//	printf("%d\n", Fib(n));
//
//	return 0;
//}

//⻘蛙跳台阶问题
//n==1 有一种跳法
//n==2 有二种跳法
//step(n-1) + step(n-2)就是n个台阶的跳法
#include<stdio.h>

int step(int n)
{
	if (n == 1)
		return 1;

	if (n == 2)
		return 2;

	return step(n - 1) + step(n - 2);
}

int main()
{
	int n = 0;
	scanf("%d", &n);
	printf("%d\n",step(n));

	return 0;
}